package main.java.com.itlin.datastructure.binarytree;

import java.util.LinkedList;

public class TreeTraversal {
    public static void main(String[] args) {

        TreeNode root = new TreeNode(
                new TreeNode( new TreeNode(4),2,null),
                1,
                new TreeNode(new TreeNode(5),3,new TreeNode(6))
        );

//        preOrder(root);
//        System.out.println();
//        inOrder(root);
//        System.out.println();
//        postOrder(root);

        //非递归方法后序遍历

        //用栈 返回节点
        LinkedList<TreeNode> stack = new LinkedList<>();

        TreeNode curr = root;// 代表当前节点
        TreeNode pop = null;//最近一次弹栈的元素
        while(curr != null || !stack.isEmpty()){
            if (curr != null) {
                //前序遍历
                //colorPrintln("去：" + curr.val,31);
                stack.push(curr);// 压入栈，为了记住回来的路
                curr = curr.left;
            }else {
                TreeNode peek = stack.peek();//栈顶元素
                if (peek.right == null || peek.right == pop){// 右子树处理完成
                    pop = stack.pop();
                    colorPrintln("回: " + pop.val,34);

                }else{
                    curr = peek.right;
                }

            }
        }

    }

    private static void colorPrintln(String origin, int color){
        System.out.printf("\033[%dm%s\033[0m%n" , color, origin);
    }

    /**
     * 前序遍历
     * @param node - 节点
     */
    static void preOrder(TreeNode node){
        if(node == null) return ;

        System.out.print(node.val + "\t");
        preOrder(node.left);
        preOrder(node.right);
    }

    /**
     * 中序遍历
     * @param node - 节点
     */
    static void inOrder(TreeNode node){
        if(node == null) return ;

        inOrder(node.left);
        System.out.print(node.val + "\t");
        inOrder(node.right);
    }

    /**
     * 后序遍历
     * @param node - 节点
     */
    static void postOrder(TreeNode node) {
        if (node == null) return;

        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.val + "\t");
    }
}
